/**
 * Created by stone on 2017/8/21.
 */
public class NodeTree<E>
{
    int data;

    NodeTree<E> left;

    NodeTree<E> right;

    public NodeTree(int data) //初始化一棵树
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }


    /**
     * @param node
     * @param data
     */
    public void insert(NodeTree<E> node, int data)
    {
        if (data > node.data)
        {
            if (null == node.right)
            {
                node.right = new NodeTree<>(data);
            }
            else
            {
                this.insert(node.right, data);
            }
        }
        else
        {
            if (null == node.left)
            {
                node.left = new NodeTree<>(data);
            }
            else
            {
                this.insert(node.left, data);
            }
        }
    }


    @Override
    public String toString()
    {
        return "NodeTree{" + "data=" + data + ", left=" + left + ", right=" + right + '}';
    }

    public static void main(String[] args)
    {
        int arr[] = { 35, 17, 39, 9, 1, 28, 65, 56, 87 };
        NodeTree<Integer> nodeTree = new NodeTree(arr[0]);
        for (int i = 0, len = arr.length; i < len; i++)
        {
            nodeTree.insert(nodeTree, arr[i]);
        }
        QueryTree.preOrder(nodeTree);
    }
}

/**
 * 遍历
 */
class QueryTree<E extends Object>

{
    /**
     * @param node
     */
    public static<E> void preOrder(NodeTree<E> node)
    {
        if (node != null)
        {
            System.out.println(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    /**
     * @param node
     */
    public static<E> void inOrder(NodeTree<E> node)
    {
        if (node != null)
        {
            inOrder(node.left);
            System.out.println(node.data);
            inOrder(node.right);
        }
    }

    /**
     * @param node
     */
    public static<E> void postOrder(NodeTree<E> node)
    {
        if (node != null)
        {
            inOrder(node.left);
            inOrder(node.right);
            System.out.println(node.data);
        }
    }
}

/**
 * 查询
 */
class FindTree
{
    public static NodeTree<Integer> find(NodeTree<Integer> root, int data)
    {
        NodeTree node = root;
        while (root.data != data)
        {
            if (root.data < data)
            {
                node = root.right;
            }
            else
            {
                node = root.left;
            }
            if (root == null)
            {
                return null;
            }
        }
        return node;
    }
}
